package codingforgreat.class44;

import sun.reflect.generics.tree.ReturnType;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Problem_0317_ShortestDistanceFromAllBuildings {
    public static int shortestDistance3(int[][] grid) {
        int pass = 0;
        int[][] dist = new int[grid.length][grid[0].length];
        int step = Integer.MAX_VALUE;
        int[] trans = new int[]{0, 1, 0, -1, 0};
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    step = bfs(grid, dist, i, j, pass--, trans);
                    if (step == Integer.MAX_VALUE) {
                        return -1;
                    }
                }
            }
        }
        return step;
    }
    public static int bfs(int[][] grid, int[][] dist, int i, int j, int pass, int[] trans) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        int level = 0;
        int ans = Integer.MAX_VALUE;
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;
            for (int k = 0; k < size; k++) {
               int[] node = queue.poll();
                for (int l = 1; l < trans.length; l++) {
                    int nextr = node[0] + trans[l - 1];
                    int nextc = node[1] + trans[l];
                    if (nextr >= 0 && nextr < grid.length && nextc >= 0 && nextc < grid[0].length
                            && grid[nextr][nextc] == pass) {
                        queue.offer(new int[] { nextr, nextc });
                        dist[nextr][nextc] += level;
                        ans = Math.min(ans, dist[nextr][nextc]);
                        grid[nextr][nextc]--;
                    }
                }
            }
        }
        return ans;
    }
}
